package com.example.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。
 *  每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人(每个人只能看到前面比自己高的人)。
 *  请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，
 *  其中 queue[j] = [hj, kj] 是队列中第j 个人的属性（queue[0] 是排在队列前面的人）。
 *
 *  示例 1：
 * 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
 * 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
 * 解释：
 * 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
 * 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
 * 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
 * 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
 * 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
 * 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
 * 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
 *
 *  示例 2：
 * 输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
 * 输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
 */
public class Leetcode406_ReconstructQueue {
    public static void main(String[] args) {
        int[][] people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
        int[][] res = new Solution().reconstructQueue(people);
        for (int[] re : res) {
            System.out.println(Arrays.toString(re));
        }
    }

    static class Solution {
        /**
         * 解法二:
         * 排序 然后 插入
         * 排序:按照第一个值降序，第二个升序排序
         * 然后遍历排序的数组，根据第二个值为索引插入到list中
         *
         * @param people
         * @return
         */
        private int[][] reconstructQueue2(int[][] people) {
            if (people == null || people.length == 0 || people[0].length == 0) return new int[0][2];
            Arrays.sort(people, (p1, p2) -> {
                if (p2[0] != p1[0]) {
                    return p2[0] - p1[0];
                } else
                    return p1[1] - p2[1];
            });
            // {{7, 0}, {7, 1}, {6, 1}, {5, 0}, {5, 2}, {4, 4}}; // 排序后的结果

            // 插入的每一步
            // {7, 0}
            // {7, 0}, {7, 1}
            // {7, 0}, {6, 1}, {7, 1}
            // {5, 0}, {7, 0}, {6, 1}, {7, 1}
            // {5, 0}, {7, 0}, {5, 2}, {6, 1}, {7, 1}
            // {5, 0}, {7, 0}, {5, 2}, {6, 1}, {4, 4}, {7, 1}

            List<int[]> resList = new ArrayList<>();
            for (int[] p : people) {
                resList.add(p[1], p);
            }

            return resList.toArray(new int[resList.size()][2]);
        }

        /**
         * 解法一：
         * 排序:按照第一个值升序，第二个值降序排序
         * 然后遍历排序后的的数组，将(第二个值 + 1) 作为该元素前面需要预留的空位
         * (因为在决定第i个人的位置时，前面的 i - 1 个人的位置都已经确定了,且前面的人都比当前这个人要矮，就可以不用关心前面已经定了的位置)
         *
         * @param people
         * @return
         */
        private int[][] reconstructQueue1(int[][] people) {
            if (people == null || people.length == 0 || people[0].length == 0) return new int[0][2];
            Arrays.sort(people, (p1, p2) -> {
                if (p2[0] != p1[0]) {
                    return p1[0] - p2[0];
                } else
                    return p2[1] - p1[1];
            });

            int[][] res = new int[people.length][];
            for (int[] pe : people) {
                int spaces = pe[1] + 1; // 需要给预留的位置
                for (int i = 0; i < res.length; i++) {
                    if (res[i] == null) { // 当前位置为null, 代表当前位置可以为预留的位置
                        --spaces;
                        if (spaces == 0) {
                            res[i] = pe;
                            break;
                        }
                    }
                }
            }
            return res;
        }

        public int[][] reconstructQueue(int[][] people) {
            return reconstructQueue2(people);
        }
    }
}
